package com.zlk.algorithm.algorithm.sort.merge;

// 小和问题
// * 在一个数组中，一个数左边比它小的数的总和，叫该数的小和 所有数的小和累加起来，叫数组小和
// * 例子： [1,3,4,2,5]
// * 1左边比1小的数：没有
// * 3左边比3小的数：1
// * 4左边比4小的数：1、3
// * 2左边比2小的数：1
// * 5左边比5小的数：1、3、4、 2
// * 所以数组的小和为1+1+3+1+1+3+4+2=16 给定一个数组arr，求数组小和
// 测试链接 : https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.*;


public class Code01_SmallSum {


	public static int MAXN = 100001;
	public static int MAXVAL  =101;

	public static int[] arr  = new int[MAXN];
	public static int n ;

	//注意： 一定要读完题意 ，特别是边界值，是大于还是大于等于，
	// 得看下数据得范围 int得数据并不一定能表示得过来

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(reader);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken()!=-1){
			n = (int) in.nval;
			for (int i = 0; i <n ; i++) {
				in.nextToken();
				arr[i] =(int)in.nval;
			}
			long ans = smallSum(arr, 0, n - 1);

			out.println(ans);
		}
		out.flush();
		out.close();
	}

	private static long smallSum(int[] arr,int l,int r) {
		if(l==r){
			return 0;
		}
		int mid = l+((r-l)>>1);
		return smallSum(arr,l,mid)+smallSum(arr,mid+1,r)+merge(arr,l,r,mid);
	}

	private static long merge(int[] arr, int l, int r, int mid) {
		int[] temp = new int[r-l+1];
		int lIndex = l;
		int rIndex = mid+1;
		int index = 0;
		long count = 0;
		// 8 4 2 1    10 8 7 5
		//
		//构建前准和
		int[] prefixArr = new int[mid+1];
		int pre = 0;
		for (int i = l; i <=mid ; i++) {
			pre+=arr[i];
			prefixArr[i]=pre;
		}


		while (lIndex<=mid&&rIndex<=r){
			if(arr[rIndex]>=arr[lIndex]){
				count+=(pre-prefixArr[lIndex]+arr[lIndex]);
				rIndex++;
			}else{
				lIndex++;
			}
		}
		lIndex = l;
		rIndex = mid+1;
		while (lIndex<=mid&&rIndex<=r){
			temp[index++] = arr[lIndex]<=arr[rIndex]?arr[rIndex++]:arr[lIndex++];
		}
		while (lIndex<=mid){
			temp[index++] =  arr[lIndex++];
		}
		while (rIndex<=r){
			temp[index++] =  arr[rIndex++];
		}
		lIndex = l;
		for (int val : temp) {
			arr[lIndex++] = val;
		}
		return count;
	}


	//    / 1 3 5 2 4 6
	//	/// 0 1 2 3 4 5
	//	// 1+4 +2+6    = 13
	//	// 1 3 5 |  2 4 6
 	//     1 10  11  |    10 14 15
	//
	private static long merge2(int[] arr, int l, int r, int mid) {
		int[] temp = new int[r-l+1];
		int lIndex = l;
		int rIndex = mid+1;
		int index = 0;
		long ans = 0;

		while (lIndex<=mid&&rIndex<=r){
			if(arr[rIndex]>=arr[lIndex]){
				ans+=(r-rIndex+1)*arr[lIndex];
				lIndex++;
			}else{
				rIndex++;
			}
		}


//
//		for (int j = mid + 1, i = l, sum = 0; j <= r; j++) {
//			while (i <= mid && arr[i] <= arr[j]) {
//				sum += arr[i++];
//			}
//			ans += sum;
//		}


		lIndex = l;
		rIndex = mid+1;
		while (lIndex<=mid&&rIndex<=r){
			temp[index++] = arr[lIndex]<=arr[rIndex]?arr[lIndex++]:arr[rIndex++];
		}
		while (lIndex<=mid){
			temp[index++] =  arr[lIndex++];
		}
		while (rIndex<=r){
			temp[index++] =  arr[rIndex++];
		}
		lIndex = l;
		for (int val : temp) {
			arr[lIndex++] = val;
		}
		return ans;
	}

}
